#include <stdio.h>
/*但是当测试用例有多个的情况下，每次重新计算第k个数据，会超时*/

int main()
{
    long int arr[1000000] = {1,2};
    for(int i = 2;i<1000000;i++){  //直接在arr中存放所有 模32767的值
        arr[i] = (arr[i - 1] * 2 + arr[i - 2]) % 32767;
    }
    int n;
    scanf("%d",&n);
    while(n--){
        int k;
        scanf("%d",&k);
        printf("%d\n",arr[k - 1]);
    }
    return 0;
}